package main


import (
	"container/heap"
	"fmt"
)
//最小堆实现
type MinHeap []int

func (h MinHeap) Len()int{
	return len(h)
}

func (h *MinHeap) Push(x interface{}){
	*h=append(*h,x.(int))
}

func (h *MinHeap) Pop() interface{} {
	tmp := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return tmp
}
func (h MinHeap) Less(i,j int)bool{
	return h[i]<h[j]
}
func (h *MinHeap) Swap(i,j int){
	(*h)[i],(*h)[j] = (*h)[j],(*h)[i]
}
func (h *MinHeap) Top() int {
	x := (*h)[0] 
	return x
}

type MedianFinder struct {
	Heapmin *MinHeap
	Heapmax *MinHeap
}


/** initialize your data structure here. */
func Constructor() MedianFinder {
	return MedianFinder{
		Heapmin:new(MinHeap),
		Heapmax:new(MinHeap),
	}
}


func (this *MedianFinder) AddNum(num int)  {
	if this.Heapmin.Len()>0 && this.Heapmin.Top() < num {
		heap.Push(this.Heapmin,num)
	}else{
		heap.Push(this.Heapmax,-num)
	}	
	if this.Heapmin.Len()-this.Heapmax.Len()==2{
		heap.Push(this.Heapmax,-(heap.Pop(this.Heapmin)).(int))
	}else if this.Heapmin.Len()-this.Heapmax.Len()==-2{
		heap.Push(this.Heapmin,-(heap.Pop(this.Heapmax)).(int))
	}
}


func (this *MedianFinder) FindMedian() float64 {
	lmn,lma:=this.Heapmin.Len(),this.Heapmax.Len()
	if lmn>lma{
		return float64(this.Heapmin.Top())
	}else if lma>lmn{
		return -float64(this.Heapmax.Top())
	}
	return (float64(this.Heapmax.Top())-float64(this.Heapmin.Top()))/2.0
}



func main(){
	h:=new(MinHeap)
	heap.Push(h,3)
	heap.Push(h,2)
	heap.Push(h,1)
	fmt.Println(h.Top())
	fmt.Println(heap.Pop(h))
	fmt.Println(h.Top())
	
 }